package org.example.leetcode;

/**
 * @author: lynn
 * @Descript: 解数独
 * @date: 2021/8/3 16:26
 * @version: 1.0
 */
public class LC37 {
    public static void main(String[] args) {

    }
    //fixme https://www.bilibili.com/video/BV1LJ41127NQ?from=search&seid=2493260419247828782
    public void solveSudoku(char[][] board) {
        //要注意，填的值一定是1-9中，可以填的最小值
        //是典型的put,check 和 unchoose的问题
        helper(board);
    }
    private boolean isValid(char[][] board,int row,int col,char n){
        for (int k = 0; k <9 ; k++) {
            if (board[row][k]==n) return false;//行
            if (board[k][col]==n) return false;//列
            //行偏移量 row 3*(row/3)
            //列偏移量 col 3*(col/3)
            //k代表在子宫格中的位置，下面的x，所处的k，是6(k是从0开始)，它在子宫格的row=6/3,col=6%3;
            if (board[3*(row/3)+k/3][3*(col/3)+k%3]==n) return false;
            //fixme 如何表示subgrid的index
            // 0 1 2 3 4 5 6 7 8
            // 1
            // 2     x
            // 3
            // 4
            // 5
            // 6
            // 7
            // 8
            // x所在的subgird 的col=4 在[3-5],subgrid 的row=1 在 [0-2]，此时x就是k，k=6
            //row 0-2
            //col 3-5

        }
        return true;
    }

    private boolean helper(char[][] board){
        for (int row = 0; row <9 ; row++) {
            for (int col = 0; col <9 ; col++) {
                if (board[row][col]=='.'){//准备投放，从小到大放
                    for (char num = '1'; num <='9' ; num++) {
                        if (isValid(board,row,col,num)){
                            board[row][col]=num;
                            if (helper(board)) return true;
                            board[row][col]='.';
                        }
                    }
                    //代表说1-9填了都不对，不写的话，就不会返回到上一级了，就接下去做for循环了
                    return false;
                }
            }
        }
        return true;
    }
}
